package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
题型： 回溯 - 排序
https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html
https://leetcode.cn/problems/permutations-ii/

47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
class leetcode_47 {
    @Test
    fun test_1() {
        val actual = permuteUnique(intArrayOf(1, 1, 2))
        val expect = arrayListOf(arrayListOf(1, 1, 2), arrayListOf(1, 2, 1), arrayListOf(2, 1, 1))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val actual = permuteUnique(intArrayOf(1, 2, 3))
        val expect = arrayListOf(arrayListOf(1, 2, 3), arrayListOf(1, 3, 2), arrayListOf(2, 1, 3), arrayListOf(2, 3, 1), arrayListOf(3, 1, 2), arrayListOf(3, 2, 1))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    fun permuteUnique(nums: IntArray): List<List<Int>> {
        /*
        回溯法
        1 树枝去重：一个数字元素只能在集合中出现一次
        2 树层去重（因为有重复数字）
        去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
        3 在叶子节点收集结果
         */
        nums.sort()
        val path: ArrayList<Int> = ArrayList<Int>()
        val result: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        backtracking(nums,path,result, BooleanArray(nums.size))
        return result
    }


    private fun backtracking(nums: IntArray, path: ArrayList<Int>, result: ArrayList<ArrayList<Int>> , used: BooleanArray) {
        // 时间复杂度: 最差情况所有元素都是唯一的。复杂度和全排列1都是 O(n! * n) 对于 n 个元素一共有 n! 中排列方案。而对于每一个答案，我们需要 O(n) 去复制最终放到 result 数组
        // T -  N X N!
        // 空间复杂度：O(n)。用 O(n) 的标记数组，同时在递归的时候栈深度会达到 O(n)
        // S - N

        // 终止条件
        if (path.size == nums.size) {
            // 收集结果
            val t: ArrayList<Int> = ArrayList<Int>()
            t.addAll(path)
            result.add(t)
            return
        }
        for (i in 0 until nums.size) { // [0, end index]
            // 处理节点
            // 树层去重
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue
            }
            // 树枝去重
            if (used[i] == true) {
                continue
            }
            path.add(nums[i])
            used[i] = true

            // 递归
            backtracking(nums, path, result, used)

            // 回溯
            path.removeAt(path.size - 1)
            used[i] = false
        }
    }
}